Tute - Completed (Week 1)

For which values of \(A\) and \(B\) does the boolean expression \(\varphi = \neg (A \Rightarrow B) \lor \neg B\) hold?

Simplify the boolean expression \((A \Rightarrow B) \lor (B \Rightarrow A)\)

A binary connective \(\bullet\) is defined as follows:

Restate the formula \(A \lor B\) in terms of \(\bullet\). What is the \(\bullet\) connective?

Assuming that \(F(x)\) states that the person \(x\) is my friend and that \(P(x)\) states that the person \(x\) is perfect, what is a logical translation of the phrase "None of my friends are perfect"?

Given the following function

\[ f (n) = \begin{cases} 0 & \text{if}\ n = 0 \\ 2n - 1 + f(n-1) & \text{if}\ n > 0 \end{cases} \]

Prove that \(\forall n \in \mathbb{N}.\ f(n) = n^2\).

1. What is the difference between a data and a type declaration?
2. What is the difference between a type and a data constructor? List the identifiers in the code which represent type names, and those which represent data constructor names.
3. Which phase of the compiler would be responsible for distinguishing type and data constructors?

data Tree a = Branch a (Tree a) (Tree a) | Leaf

1. Write a Haskell function mySum that sums all elements in a list of numbers. Feel free to use the following template:

   mySum :: [Int] -> Int
   mySum []     = ???
   mySum (n:ns) = ???
   

2. Write a Haskell function myProduct that multiplies all elements in a list of numbers.

3. You probably used copypaste to solve the previous question, didn't you? No reason to be ashamed, we've all done it! But let's try not to.

   Find a generalisation myBinop that applies a given binary operator f with unit element z to a list of numbers. We will then be able to define myProduct and mySum using myBinop.

   myBinop :: (Int -> Int -> Int) -> Int -> ([Int] -> Int)
   myBinop f z [] = ???
   myBinop f z (n:ns) = ???
   
   mySum :: [Int] -> Int
   mySum ns = myBinop (+) 0 ns
   
   myProduct :: [Int] -> Int
   myProduct ns = myBinop (*) 1 ns
   

4. We just reinvented a wheel. The fold functions are general-purpose library functions that completely subsume myBinop. Try to implement mySum and myProduct using foldr instead of myBinop.

   The linked library documentation references a lot of concepts that we don't assume familiarity with, so don't worry if you don't fully understand it. Perhaps start by looking at the examples.

mySum :: [Int] -> Int
mySum [] = 0
mySum (n:ns) = n + mySum ns

myProduct :: [Int] -> Int
myProduct [] = 1
myProduct (n:ns) = n*myProduct ns

myBinop :: (Int -> Int -> Int) -> Int -> ([Int] -> Int)
myBinop f z [] = z
myBinop f z (n:ns) = n `f` myBinop f z ns

mySum2 :: [Int] -> Int
mySum2 = myBinop (+) 0

myProduct2 :: [Int] -> Int
myProduct2 = myBinop (*) 1

mySum3 :: [Int] -> Int
mySum3 = foldr (+) 0

myProduct3 :: [Int] -> Int
myProduct3 = foldr (*) 1